home *** CD-ROM | disk | FTP | other *** search
/ Black Crawling Systems Archive Release 1.0 / Black Crawling Systems Archive Release 1.0 (L0pht Heavy Industries, Inc.)(1997).ISO / blackcrwl / encrypt / RSAISBRO.TXT < prev    next >
Text File  |  1996-06-08  |  12KB  |  363 lines
  1. Here are the details why RSA is broken (so Ada developers of RSA
  2. and DES algorithms will know).
  3.  
  4. What follows is in three sections: 
  5.  
  6.      1.  The 1990 DRAFT paper by Bill Payne "Public Key Cryptography
  7. is Easy to Break";
  8.  
  9.      2.  What Burt Kaliski of RSA "posted to sci.crypt a few days ago"
  10. from January 25, 1994 [which this reader must have missed];  and
  11.  
  12.      3.  The letter of Bill Payne to Kaliski of January 30, 1994
  13. pointing out an enormous blunder by Kaliski in his "post". 
  14.  
  15.  
  16. - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 
  17.  
  18.  
  19.                            DRAFT
  20.  
  21.           Public Key Cryptography is Easy to Break
  22.  
  23.                       William H. Payne
  24.                 Sandia National Laboratories
  25.                       October 16, 1990
  26.  
  27.                           ABSTRACT
  28.  
  29. Public key, also known as Rivest, Shamir, and Adleman,
  30. cryptography is broken without factoring the modulus m.
  31. The product of the encryption and the decryption exponent is
  32. computed directly with order log(base-2) m shifts, adds, and compares.
  33. A continued product between the modulus and its multiplier which
  34. matches a criterion solves the Fermat-Euler theorems simply for
  35. even large moduli.
  36.  
  37.                            DRAFT
  38.  
  39. Euler's theorem states
  40.  
  41.                    phi(m) -
  42.                   a       -  1 mod m
  43.                           -
  44.  
  45. for a relatively prime to m where phi(m) is the number of numbers
  46. less than and relatively prime to m.  For prime p and q, phi(pq) =
  47. (p-1)(q-1).  For example, if p=5 and q=7, then (5x7) =
  48. 4x6=2x2x2x3=24.  Then for any number of relatively prime to m, say
  49. 2,
  50.                    24  -
  51.                   2    - 1 mod 35
  52.                        -
  53.  
  54. Euler's theorem does not mean that 24 is the smallest value for
  55. which the equality is true.  The values 2, 4, 8, 6, and 12 must
  56. also be checked to determine if they too may solve the equation.
  57.  
  58. Here is an algorithm to solve Euler's theorem but it does not
  59. require factoring the modulus (from which the exponent is
  60. computed).  The algorithm is extremely simple and obviously
  61. correct (to those who think in binary).  Its explanation is best
  62. done by example so the reader can intuitively understand its 
  63. importance and practical ramifications.
  64.  
  65. The smallest even prime 2 is relatively prime to any odd modulus.
  66. Therefore,
  67.                    x   -
  68.                   2    -  1 mod 35
  69.                        -
  70.  
  71. for some value of x.  This means that
  72.  
  73.                    x      
  74.                   2  - 1  = 35y
  75.                                   x
  76. for some value of y.  A solution 2  -1 is represented in binary
  77. as
  78.                                    1
  79.                                   11
  80.                                  111
  81.                                 1111
  82.                                11111
  83.                                    .
  84.                                    .
  85.                                    .
  86.  
  87. for some value of x.  Computation of 35y must be one of these
  88. values.  Computation of y is easy.  35 in binary is 100011.  A
  89. product of 35 times y is developed from right to left forcing the
  90. low order bits to one.  The algorithm terminates when the high
  91. six bits are all one.  Here is the algorithm computation.
  92.  
  93.                         1 0 0 0 1 1
  94.                     1 0 0 0 1 1
  95.                   ------------------
  96.                     1 0 1 0 1 1 1 1
  97.                 1 0 0 0 1 1
  98.                ---------------------
  99.                 1 0 1 1 0 1 1 1 1 1
  100.               1 0 0 0 1 1
  101.              -----------------------
  102.               1 1 1 0 0 1 1 1 1 1 1
  103.             1 0 0 0 1 1
  104.            -------------------------
  105.             1 1 1 1 1 1 1 1 1 1 1 1
  106.  
  107.          12 11 10 9 8 7 6 5 4 3 2 1
  108.  
  109. which means
  110.                    12  -
  111.                   2    -  1 mod 35
  112.                        -
  113.  
  114. One are developed for the low order bits of the computation by
  115. shift and add.  At each step of the algorithm the high order six
  116. bits are checked to see if they are all one.  If so (the
  117. termination criterion) then algorithm terminates, and the solution
  118. is immediate.
  119.  
  120. The algorithm finds the least value for which equality is true.
  121.  
  122. The modulus can be a product of any number of primes excluding
  123. two, and the algorithm continues to work.
  124.  
  125. The amount of work required for the algorithm to complete is a
  126. linear function of the number of bits in the modulus.  Fermat's
  127. theorem gives a good example of the worst case amount of work for
  128. the theorem to execute.  The algorithm finds x such that
  129.  
  130.                    x   -
  131.                   2    -   1 mod 13
  132.                        -
  133.  
  134. Here are the computations.
  135.  
  136.                             1 1 0 1
  137.                           1 1 0 1
  138.                         ------------
  139.                         1 0 0 1 1 1
  140.                       1 1 0 1
  141.                    -----------------
  142.                     1 0 0 0 1 1 1 1
  143.                     1 1 0 1
  144.                  -------------------
  145.                   1 0 1 0 1 1 1 1 1
  146.                   1 1 0 1
  147.                ---------------------
  148.                 1 0 1 1 1 1 1 1 1 1
  149.             1 1 0 1
  150.            -------------------------
  151.             1 1 1 1 1 1 1 1 1 1 1 1
  152.  
  153.          12 11 10 9 8 7 6 5 4 3 2 1
  154.  
  155. or
  156.                    12   -
  157.                   2     -   1 mod 13.
  158.                         -
  159.  
  160.  
  161. The author discovered this result between 8:30 and 10:08 PM on
  162. October 15, 1990.  Implications of the algorithm are great.*
  163.  
  164. The author thanks Michael O. Vahle for conversations on 
  165. strategies to break public key encryption which spanned several
  166. years.
  167.  
  168. * More than Euclid's algorithm?
  169.  
  170.  
  171. - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 
  172.  
  173.  
  174. Posted to sci.crypt:
  175. ------ -- ----------
  176.  
  177. Bill Payne sent me a copy of his paper "Public Key Cryptography
  178. is Easy to Break" and gave me permission by phone to post
  179. a description.
  180.  
  181. The quick summary is that his result, wile clever, actually 
  182. confirms that RSA is still hard to break.  Payne says he has 
  183. better methods, though, which he hasn't published.
  184.  
  185.  
  186. RSA BACKGROUND
  187.  
  188. An RSA key pair consists of a public key (n,e) and a private 
  189. key (n,d), where n, the RSA modulus, is the product of distinct
  190. primes p and q, and where e and d (respectively the public and
  191. private exponents) satisfy the equation
  192.  
  193.                 ed = 1 mod (p-1)(q-1)
  194.  
  195.  
  196. To break RSA (i.e., solve the private key, given the public 
  197. key), one need only find the product (p-1)(q-1), which is usually 
  198. denoted phi(n).  Given phi(n) one can easily find p and q, so a 
  199. method that finds phi(n) also factors n.
  200.  
  201.  
  202. PAYNE'S RESULTS
  203.  
  204. According to Fermat's little theorem, for all a, one has
  205.  
  206.                a^phi(n) = 1 mod n
  207.  
  208. Consequently, for a=2, one has that 2^phi(n)-1 is divisible by n.
  209. One can therefore find phi(n) (or a divisor of it) by constructing
  210. a multiple of n whose binary representation is all 1's.
  211.  
  212. Payne's algorithm finds such a multiple by simple binary 
  213. operations.  The algorithm sets bits of an accumulator to 1 by 
  214. adding shifts of the modulus n, working from least significant to
  215. most significant bit of the accumulator.  Eventually the 
  216. accumulator is all 1's, and the number of 1's yields a divisor 
  217. of ph(n).
  218.  
  219. Here is the algorithm:
  220.  
  221.         x := 0
  222.         i := 0
  223.         while x contains a 0 bit (other than leading bits) do
  224.              if bit i of x is 0
  225.                   then x:= x + ( n << i)
  226.              i := i + 1
  227.         return length of x in bits
  228.  
  229. By considering only the window of bits starting at bit i, one 
  230. can view Payne's algorithm as applying repeatedly the following 
  231. permutation on the set { 0, ... , n-1 }:
  232.  
  233.  
  234.                  / (w + n - 1) / 2  if w is odd
  235.            f(w) |
  236.  
  237.                  \ (w - 1) / 2      if w is even   
  238.  
  239.  
  240. The window w at iteration i corresponds to the accumulator value 
  241. x = 2^i w + 2^i - 1.  Since the function f is a permutation, 
  242. repeated application of f will eventually return to any given 
  243. starting value.  To find a multiple of n whose binary 
  244. representation is all 1's, it suffices to start with w = 0.  
  245. When repeated application of f arrives at w = 0 again, the value
  246. x = 2^i -1  will be a multiple of n whose binary representation 
  247. is all 1's.
  248.  
  249. There's only one problem:  Finding x can take up to ph(n) steps!
  250. Since phi(n) is almost as large as n, if n is just ten digits
  251. long (not to mention the hundreds of digits in RSA), the amount
  252. of work is enormous.  Indeed, this is an "exponential-time"
  253. algorithm for finding phi(n), the slowest kind.  While Payne's
  254. algorithm is curious, public key is no easier to break.
  255.  
  256.  
  257.  
  258. - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 
  259.  
  260.  
  261. January 30, 1994
  262.  
  263. Burt Kaliski, Chief Scientist
  264. RSA Laboratories
  265. 100 Marine Parkway
  266. Redwood City, CA  94065
  267. 415-595-7703
  268.  
  269. Dear Burt:
  270.  
  271. Thank you for your January 25, 1994 letter and sci.crypt posting
  272. of my DRAFT paper results.  I attach a copy for your immediate
  273. reference.
  274.  
  275. I realize that the subject breaking RSA without factoring may
  276. be painful to you.  I commiserate.
  277.  
  278. I found your explanation interesting in several respects.  I
  279. liked your explanation on the last page in terms of w.  Very
  280. perceptive.
  281.  
  282. There may be an incorrect statement in your posting.
  283.  
  284. Your statement, "Given phi(n) one can easily find p and q, so a
  285. method that finds phi(n) also factors n.", I believe is false.
  286.  
  287. Knowledge of phi(n) does not always lead to factors of n.
  288.  
  289. Let me give you a counter-example.  Phi(7 x 31) = phi(7) x phi(31)
  290. = 6 x 30 = 180.  And phi(19 x 11) = phi(19) x phi(11) = 18 x 10
  291. = 180 !
  292.  
  293. Do you agree?  More than one product of two primes can map into 
  294. the same totient!
  295.  
  296. Even if phi(n) leads to factors of n, phi(n) must be factored.
  297. This could be a major computational task.
  298.  
  299. Jim Omura told me that my algorithm is the first algorithm Omura
  300. has seen which breaks RSA without factoring.
  301.  
  302. If you agree with my counter-example and Omura's opinion, then
  303. perhaps you might post a statement on sci.crypt.
  304.  
  305. Your statement, "There's only one problem:  Finding x can take up
  306. to phi(n) steps." may be, I believe inaccurate.  But your 
  307. statement is correct.  Let me explain this apparent anomaly.
  308.  
  309. You apparently do not know about indefinite division.
  310.  
  311. The algorithm in my DRAFT paper generates a series of even
  312. numbers.  The algorithm DRAFT paper I sent you did this from
  313. right to left termination, as you wisely pointed out, w = 0.
  314.  
  315. But a similar algorithm also works left to right.  Indefinite
  316. division, I call it.  I mentioned this in my January 4, 1994
  317. letter to you.  I attach a copy for immediate reference.
  318.  
  319. Therefore, the two algorithms can work simultaneously and meet in
  320. the middle of the sequence of even numbers.  Phi(n)/2 maximum.
  321. Not phi(n).
  322.  
  323. I quote from my January 4 letter to you, "Public key has big
  324. problems.  I believe that the problems will _slowly_ come to
  325. light."
  326.  
  327. You have my permission to post these observations on sci.crypt.
  328.  
  329. I am sensitive to your statement "Bill Payne sent me a copy of
  330. his paper".  I sent you a copy of a DRAFT paper.
  331.  
  332.  .....
  333.  
  334. Sincerely,
  335.  
  336. /s/ Bill
  337.  
  338. Bill Payne
  339. 13015 Calle de Sandias NE
  340. Albuquerque, NM  87111
  341. 505-292-7037
  342.  
  343.  
  344. - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 
  345.  
  346. Note:  Thanks are due to Mark Riordan (mrr@scss3.cl.msu.edu) who 
  347.        posts regularly to sci.crypt and has kindly agreed to
  348.        post this message to sci.crypt for this transcriber, Colin
  349.        James III (cjames@dsc.blm.gov).
  350.  
  351. - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 
  352.  
  353.  
  354.  
  355. Disclaimer:  The opinions expressed here are responsible for their
  356. ~~~~~~~~~~~  content; all email is published at my sole discretion.
  357. - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 
  358. Colin James III          cjames@dsc.blm.gov          (303) 236-5897
  359. Work:       BLM, SC-342D, Bldg 50, DFC,    Denver,   CO  80225-0047          
  360. Residence:  CEC Services, 2080 Kipling St, Lakewood, CO  80215-1502
  361. (303) 231-9437 Voice  [cjames@microksy.org & cojames@nyx.cs.du.edu]
  362. (303) 231-9438 Fax and Windows NT RAS to Ada repository (ftp soon!)
  363.